package cn.zhl.leetcode.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: demos
 * @description: https://leetcode-cn.com/problems/invert-binary-tree/
 * @author: 刘振华
 * @create: 2020-04-17 19:30
 **/
public class _226_翻转二叉树 {
	/*
	翻转一棵二叉树。

示例：

输入：

	 4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

	 4
   /   \
  7     2
 / \   / \
9   6 3   1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 */
	public TreeNode invertTree(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		if (root != null) {
			queue.offer(root);
			while (!queue.isEmpty()) {
				TreeNode node = queue.poll();
				TreeNode left = node.left;
				TreeNode right = node.right;
				if (left != null) {
					queue.offer(left);
				}
				if (right != null) {
					queue.offer(right);
				}
				node.left = right;
				node.right = left;
			}
		}
		return root;
	}
}
